<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            时间：O(N^2)
            空间：O(N)
        */
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        var buildTree = function (inorder, postorder) {
            // 退出条件
            if (inorder.length === 0 || postorder.length === 0) {
                return null
            }

            // 后序数组最后一个元素
            let lastVal = postorder.pop()
            let deli;
            for (deli = 0; deli < inorder.length; deli++) {
                // 在中序中找到这个元素
                if (inorder[deli] === lastVal) {
                    break
                }
            }
            // 头结点是postorder的最后一个元素
            let root = new TreeNode(lastVal)

            /* 
                后序是[9, 15, 7, 20, 3] pop出最后的3
                中序是[9, 3, 15, 20, 7], 切割为[9] 和 [15, 20, 7] 而9都在左子树，[15,20,7]都在右子树
                后序此时是[9, 15, 7, 20]，3已经pop出去了，此时切割为[9] 和 [15, 7, 20]

                紧接着
                [9]和[9] root.left递归
                [15, 20, 7]和[15, 7, 20] root.right递归
            */
            const leftInorder = inorder.slice(0, deli)
            const leftPostorder = postorder.slice(0, deli)

            const rightInorder = inorder.slice(deli + 1)
            const rightPostorder = postorder.slice(deli)

            root.left = buildTree(leftInorder, leftPostorder)
            root.right = buildTree(rightInorder, rightPostorder)
            // 返回内容
            return root
        };
        let inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
        // let inorder = [3, null, 4, 1, 5, 2, 6], postorder = [3, 4, null, 5, 6, 2, 1]
        console.log(buildTree(inorder, postorder));
    </script>
</body>

</html>